With the explosive growth of the amount of information available on Internet, search engines have been increasingly relied on to retrieve desired information from databases and/or webpages. A search engine can respond to a search query submitted by a user and can return one or more search results. Generally, a search query may be composed of any type of characters recognizable by the search engine and has to be specifically representative of the desired information for the search engine to locate it from the databases or webpages and return a correct search result.
For numerous reasons, a search engine user often submits a search query that is misspelled, inaccurate, and/or poorly correlated to the desired information stored in a database, and so does not obtain desired search result. Especially, information is often organized and indexed in databases in a manner that deviates from common-sense or popular expectation, causing difficulty trying to find an average user to find a representative query expression that matches the desired information based his or her intuition. Without getting the right or expected result, a user is usually forced to formulate a number of different search queries and iteratively run the search engine. The process is non-economical, time-consuming, frustrating and sometimes futile. In the situation that a user searches for items to purchase, an unsuccessful search experience can directly cause loss of potential transactions with the user.
A commonly adopted approach to facilitate a search process is to automatically generate and suggest alternative search queries after a user submits an initial and non-matching query. Conventionally, these suggested alternatives are merely generated based on semantic similarity or relatedness to the initial query, and are not adapted to the contents of the databases being searched and the associated search history. Although useful in correcting typos in an initial query, these query suggestions may be as impertinent as the initial query to obtain the desired search result. For example if the initial query had contained no typo but yet directs the search engine to an unintended category of subject matter.